package com.yvon.service.demo.algorithm.sort;


/**
 * @author : Yvon
 * @since : 2021-10-11
 */
public class SortTest {


    public static void main(String[] args) {
        int[] a = {5,2,3,1,6,0,2,3};
        System.out.print("排序前：");
        for (int i = 0; i < a.length -1; i ++) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
        quickSort(a, 0, a.length -1);
        System.out.print("快速排序：");
        quickSort(a, 0, a.length - 1);
        for (int i = 0; i < a.length -1; i ++) {
            System.out.print(a[i] + " ");
        }


    }

    /**
     * 插入排序
     *
     * @param arr 加勒比海盗
     * @return void
     * @author : Yvon / 2021-10-11
     */
    public static void insertSort(int[] arr) {
        System.out.print("插入排序：");
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 1; i < arr.length; i ++ ) {
           for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j --) {
               arr[j] = arr[j] ^ arr[j + 1];
               arr[j + 1] = arr[j]^arr[j + 1];
               arr[j] = arr[j] ^ arr[j + 1];
           }
        }
    }


    /**
     * 冒泡排序
     *
     * @param arr 加勒比海盗
     * @return void
     * @author : Yvon / 2021-10-11
     */
    public static void bubbleSort(int[] arr) {
        System.out.print("冒泡排序：");
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i ++ ) {
            for (int j = 0; j < arr.length -1 - i; j ++ ) {
                if (arr[j] > arr[j + 1]) {
                    arr[j] = arr[j] ^ arr[j + 1];
                    arr[j + 1] = arr[j]^arr[j + 1];
                    arr[j] = arr[j] ^ arr[j + 1];
                }
            }
        }
    }

    /**
     * 快速排序
     *
     * @param arr 加勒比海盗
     * @param l   l
     * @param r   r
     * @return void
     * @author : Yvon / 2022-04-26
     */
    public static void quickSort(int[] arr, int l, int r) {
        if (r < l || arr.length < 2) {
            return;
        }
        int i,j,x;
        i = l;
        j = r;
        x = arr[i];
        while (i < j) {
            while (i < j && arr[j] >= x) {
                j --;
            }
            while (i < j && arr[i] <= x) {
                i ++;
            }
            if (i <= j) {
                int tem = arr[i];
                arr[i] = arr[j];
                arr[j] = tem;
                i --;
                j ++;
            }
            quickSort(arr, l, i);
            quickSort(arr, j, r);
        }
    }

    public static void quick(int[] arr, int l, int r) {
        if (r < l || arr.length < 2 ){
            return;
        }
        int i, j, x;
        i = l;
        j = r;
        x = arr[i];
        while (i < j) {
            while (i < j && arr[j] >= x ) {
                j--;
            }
            while (i < j && arr[i] <= x) {
                i++;
            }
            if (i <= j) {
                int temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                j++;
                i--;
            }
            quickSort(arr, l, i);
            quickSort(arr, j, r);
        }

    }
}
